package isValid;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}') {
                if(stack.isEmpty()) return false;
                if(s.charAt(i) == ')' && stack.pop() != '(') return false;
                if(s.charAt(i) == ']' && stack.pop() != '[') return false;
                if(s.charAt(i) == '}' && stack.pop() != '{') return false;
            } else {
                stack.push(s.charAt(i));
            }
        }
        return true;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while (cur!=null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            list.add(stack.peek().val);
            cur = stack.pop().right;
        }
        return list;
    }
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        dfs(list,root);
//        return list;
//    }
//    private void dfs(List<Integer> list,TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        dfs(list,root.left);
//        list.add(root.val);
//        dfs(list,root.right);
//    }
}
